package org.lex.collection.tree.builder;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.lex.collection.tree.ITreeNode;
import org.lex.collection.tree.TreeNode;
import org.lex.collection.tree.TreeNodeHelper;

public class TreeBuilder {
	private TreeNodeHelper helper = new TreeNodeHelper();

	// ========================================
	// build ITreeNode hiberarchy from TreePath
	// ========================================
	public void addTreePath(ITreeNode parent, Object[] treePath) {
		for (Object nodeData : treePath) {
			ITreeNode node = helper.searchChild(parent, nodeData);
			if (null == node) {
				node = new TreeNode(nodeData);
				parent.addChild(node);
			}
			parent = node;
		}
	}

	@SuppressWarnings("unchecked")
	public void binaryAddTreePath(ITreeNode parent, Object[] treePath, Comparator nodeComparator) {
		for (Object nodeData : treePath) {
			int index = helper.binarySearchChild(parent, nodeData, nodeComparator);
			ITreeNode node = null;
			if (index < 0) {
				index = -index - 1;
				node = new TreeNode(nodeData);
				parent.insertChild(node, index);
			} else {
				node = parent.getChild(index);
			}
			parent = node;
		}
	}

	// ========================================
	// build ITreeNode hiberarchy from NodeData
	// ========================================
	public ITreeNode buildTree(Object[][] datas) {
		List<NodeData> list = new ArrayList<NodeData>(datas.length);
		for (Object[] row : datas) {
			list.add(new NodeData(row[0], row[1], row[2]));
		}
		return buildTree(list);
	}

	public ITreeNode buildTree(NodeData... datas) {
		return buildTree(Arrays.asList(datas));
	}

	public ITreeNode buildTree(Collection<NodeData> datas) {
		Map<Object, ITreeNode> idNodeMap = new HashMap<Object, ITreeNode>();
		for (NodeData d : datas) {
			TreeNode node = new TreeNode(d.data);
			idNodeMap.put(d.id, node);
		}
		ITreeNode root = null;
		for (Object id : idNodeMap.keySet()) {
			ITreeNode current = idNodeMap.get(id);
			NodeData nodeData = this.findById(datas, id);
			Object parentId = nodeData.parentId;
			if (null != parentId) {
				ITreeNode parentNode = idNodeMap.get(parentId);
				if (null == parentNode) {
					System.err.println(nodeData + "'s parent not found!");
					return null;
				} else {
					parentNode.addChild(current);
				}
			} else {
				// root node's parentId is null
				root = current;
			}
		}
		return root;
	}

	public NodeData findById(Collection<NodeData> datas, Object id) {
		for (NodeData d : datas) {
			if (d.id.equals(id)) {
				return d;
			}
		}
		return null;
	}
}
